1. Field of the Invention
The present invention relates to high-capacity switch architectures for communication systems, and more particularly to scalable switch architectures with distributed arbitration logic.
2. Description of Related Art
High-capacity communication switch architectures have been developed to address the growing numbers of users and uses of communication networks. The switch architectures are based on a variety of switch fabric designs, which includes a shared media switch in which either memory or bus resources are shared using time division multiplexing, a stacked Banyan, a mesh switch, a crossbar switch and others. There are various advantages and disadvantages of each type.
In the implementation of high-capacity communication switches, the establishment of connections between ports on the switches is made in response to the traffic flowing through the switch. The connections are made in switching cycles that allow for efficient use of the resources. In each switching cycle of some embodiments, an arbitration process is executed by which competition for the use of the ports on the switches is resolved. As the number of ports on a given switch increases, the complexity of arbitrating among the ports increases dramatically and requires an equivalent increase in processing power. Such arbitration must be executed efficiently and quickly so that the performance of the switch is maintained. However, the computation of optimal connection maps within the switch among a large number of possible routes can be a difficult problem in dynamically changing conditions.
It is often desirable to add capacity to a given switching system. The mesh type switch and the crossbar type switch are both capable of high-capacity switching, and have extendable architectures. The crossbar switches are believed to be suited for more efficient extensions in size by adding additional crossbar planes to a stack of crossbar planes, than are mesh type architectures. So for the purpose of understanding the present invention, the basic components of a prior art crossbar architecture are shown in FIG. 1.
A generalized crossbar as shown in FIG. 1 includes a plurality of satellites S#1 through S#s, where the satellites correspond to network ports, router elements, line cards or other interface structures between communication networks and the switch fabric. The satellites communicate through a plurality of crossbars X-1 through X-m. The satellites communicate with the crossbars through respective sets of satellite to crossbar S2X links 1-1 to 1-x for satellite S#1, and s-1 though s-y for satellite S#s. The aggregate bandwidth for the satellite S#1 is expressed as the summation of the bandwidth of each of the satellite to crossbar links. The number of links from a satellite to a crossbar is dependent upon a particular implementation of the satellite, and may include one or more links per crossbar plane. The satellites include a plurality of links L to the communication channels external to the switch. In the example shown, the satellite S#1 includes n links within aggregate bandwidth equal to the summation of the bandwidth of each of the n links. The input bandwidth from the communication channel over the links L need not be equal to the bandwidth between the satellite and a crossbar over the links S2X, for buffered satellites.
A central arbitration entity 10 is coupled with the crossbars and communicates with each of the satellites through a control communication channel. The control communication channel 11 may be an inband channel which steals cycles from the crossbar switch, or any other type of communication media. A multiple plane crossbar switch, like that shown in FIG. 1, may support static grouping of the fabric pipes, where a group is formed by logically joining links between satellites and a crossbar. In this case, a transmission across a group must request a plurality of elements through the crossbar in order to make a single connection, with a wider bandwidth because of the multiple paths. Thus, for example, if the switch is configured into groups of two crossbar to satellite links, the switch operates at twice the bandwidth with half the port count. In any event, the generalized crossbar architecture of FIG. 1 supports a wide variety of bandwidth and port count configurations. However, the central arbitration entity limits the scalability of the structure because of the increasing complexity encountered as the number of satellite to crossbar links is increased.
With this background, and an understanding of the need for an improved arbitration algorithms for complex switches, it can be understood that a need exists for improved arbitration structures for complex communication switches.